package cn.edu.xjtu.work.leafSimilar;

import java.util.ArrayList;
import java.util.List;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 872. 叶子相似的树
 * 
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 * 
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 * 
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/leaf-similar-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaf1 = new ArrayList<>();
        List<Integer> leaf2 = new ArrayList<>();
        getLeaf(root1, leaf1);
        getLeaf(root2, leaf2);
        return leaf1.equals(leaf2);
    }

    public void getLeaf(TreeNode root, List<Integer> leaf) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leaf.add(root.val);
        }
        getLeaf(root.left, leaf);
        getLeaf(root.right, leaf);
    }
}
